Many network devices, such as routers, maintain one or more packet buffers or queues (e.g., first-in-first out (FIFO)) that buffer packets that are scheduled to go out on the device. These queues accommodate for momentary differences between input and output bandwidth capacities. For example, if a network device has multiple network interfaces, it may have multiple queues—one for each interface—that hold packets that are scheduled to go out on the corresponding interface.
Under heavy network traffic conditions, it is possible for these queues to become filled. When is queue is full, any new packets that are scheduled to go into the queue are typically dropped. This technique is called a drop-tail: a packet is put onto the queue if its usage is less than its maximum size, and the packet is dropped otherwise. Such packet dropping can lead to undesirable network performance, since packets are dropped based on a single factor: buffer availability. Drop-tail tends to unfairly penalize certain types of network traffic, such as bursty flows.
One technique that router manufactures have used to mitigate against drop-tail is to provide queues of larger size in their network devices. Larger queues can prevent packet dropping in a greater variety of network conditions than smaller buffers. However, larger queues have undesirable side effects, including (i) increased latency—since packets must work their way through a larger buffer, and (ii) poor responsiveness of network congestion detection methods. The practice of oversizing queues has been termed tufferbloat, and is considered to be a significant and worsening problem in networking.
Active Queue Management (AQM) techniques have been developed to mitigate against drop-tail and bufferbloat. AQM techniques generally drop certain packets probabilistically, based on a variety of factors, before the buffer is full, so that drop-tail and excessively large queues can be avoided.
For example, one AQM technique is Random Early Detection (RED) and its derivatives. If queue usage grows beyond a lower threshold, RED computes a drop probability proportional to the total queue length. If the queue length grows beyond an upper limit, RED always drops arriving packets. However, RED can be difficult to configure, since the appropriate upper and lower thresholds—which must be manually configured—depend on anticipated traffic conditions.
Another AQM technique, BLUE, is a network load based technique that increases the drop probability if it detects packet loss caused by buffer overflow. BLUE decreases the drop probability when the link becomes idle. However, with BLUE user must manually choose appropriate values for the step sizes for the increase and decrease in drop probability.
Controlled Delay (CoDel) and Proportional Integral Enhanced (PIE) are more recent AQM techniques that focus on queuing delay or sojourn time. CoDel begins to drop packets only after the queuing delay is above a threshold of 100 ms for a duration of a 5 ms threshold. CoDel increases the number of dropped packets as long as the queuing delay is above the 5 ms threshold. Using CoDel, packet drops are not probabilistic. Instead, they are based on time. CoDel exponentially decreases the time between packet drops until the queuing delay is reduced below the 5 ms threshold. PIE is a linear feedback control system with thresholds of queuing delay and maximum queue length. Its parameters include deviation from a target queue delay and a balance between queuing delay deviation and jitter.
While these, and other, AQM techniques have had some moderate success at mitigating against drop-tail and bufferbloat, existing AQM techniques all depend upon the specification of thresholds or wide-scale pre-tuning of parameters for different conditions. As such, AQM techniques can be difficult for the average administrator to properly deploy, and do not perform well in networks that have changing traffic conditions.